class Solution(object):
    def wiggleSort(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        DP = [0] * 5001
        for i in range(n):
            DP[nums[i]] += 1
        index = 5000
        i = 1
        while i < n:
            while DP[index] == 0:
                index -= 1
            DP[index] -= 1
            nums[i] = index
            i += 2
        i = 0
        while i < n:
            while DP[index] == 0:
                index -= 1
            DP[index] -= 1
            nums[i] = index
            i += 2
        return nums


data = Solution()
nums = [1, 1, 1, 1, 6, 4, 5, 7]
print(data.wiggleSort(nums))
nums = [1, 3, 2, 2, 3, 1]
print(data.wiggleSort(nums))
nums = [1, 4, 3, 4, 1, 2, 1, 3, 1, 3, 2, 3, 3]
print(data.wiggleSort(nums))
nums = [1, 5, 1, 1, 6, 4]
print(data.wiggleSort(nums))
nums = [4, 5, 5, 6]
print(data.wiggleSort(nums))
